#!/usr/bin/python
# vim: set fileencoding=utf-8 :
# Congruence Relation between two integer numbers 'a' and 'b' modulus 'n'.

from hexaInt import aInt
from hexaPosInt import posInt
from hexaLinCombi import linearCombination as lC

Exception001 = "No Integer"
Exception002 = "No posInt"
Exception003 = "No same modulus"
Exception004 = "No >0"

class myException(BaseException) :
    def __init__(self, msg="Error: ", value=0) :
        print msg, value


class congruentRelation :
    """Class Congruent Relation.
    """
    def __init__(self, a, b, n) :
        """ Instantiates a Congruent Relation so a ≡ b mod(n).
        """
        self.a = a
        self.b = b
        self.n = n

    def __str__(self) :
        """ Print congruent relation.
        """
        return str(self.a) + " ≡ " + str(self.b) + " mod(" + str(self.n) + ")"

    def isCongruentRelation(self) :
        """1.3.1. Definition. Let 'n' be a positive integer.
        Integers 'a' and 'b' are said to be congruent modulo 'n' if they have the same remainder when divided by 'n'.
        This is denoted by writing a ≡ b(mod n)
        """
        res01 = ( (self.a % self.n) == (self.b % self.n) )

        """1.3.2. Proposition. Let 'a', 'b', and n > 0 be integers.
        Then a ≡ b (mod n) if and only if n | (a-b).
        When working with congruence modulo 'n', the integer 'n' is called the modulus.
        By the preceding proposition, a ≡ b (mod n) if and only if a-b=nq for some integer 'q'.
        We can write this in the form a=b+nq, for some integer 'q'.
        This observation gives a very useful method of replacing a congruence with an equation (over Z).
        On the other hand, Proposition 1.3.3 shows that any equation can be converted to a congruence modulo 'n' by simply changing the = sign to ≡ .
        In doing so, any term congruent to 0 can simply be omitted.
        Thus the equation a=b+nq would be converted back to a ≡ b (mod n).
        """
        res02 = False
        r = abs(self.a - self.b)
        q1 = r / self.n
        ql = []
        for qq in range(q1 - 2, q1 + 2) :
            ql.append(aInt(qq))
        for q in ql :
            if (q * self.n) == r :
                res02 = True
                break
        return ( res01 and res02 )

    def __add__(self, y) :
        """1.3.3 Proposition (addition). Let n > 0 be an integer.
        Then the following conditions hold for all integers a, b, c, d:
        (a) If a  ≡  c (mod n) and b  ≡  d (mod n), then a + b  ≡  c + d (mod n).
        (b) If a + c  ≡  a + d (mod n), then c  ≡  d (mod n).
        """
        if hasattr(y, 'a'):
            return congruentRelation(self.a + y.a, self.b + y.b, self.n)
        else :
            return congruentRelation(self.a + y, self.b + y, self.n)

    def __sub__(self, y) :
        """1.3.3 Proposition (substraction). Let n > 0 be an integer.
        Then the following conditions hold for all integers a, b, c, d:
        (a) If a  ≡  c (mod n) and b  ≡  d (mod n), then a - b  ≡  c - d (mod n).
        (b) If a - c  ≡  a - d (mod n), then c  ≡  d (mod n).
        """
        if hasattr(y, 'a'):
            return congruentRelation(self.a - y.a, self.b - y.b, self.n)
        else :
            return congruentRelation(self.a - y, self.b - y, self.n)

    def __mul__(self, y) :
        """1.3.3 Proposition (proporcionality). Let n > 0 be an integer.
        Then the following conditions hold for all integers a, b, c, d:
        If ac  ≡  ad (mod n) and (a,n)=1, then c  ≡  d (mod n).
        """
        if hasattr(y, 'a'):
            return congruentRelation(self.a * y.a, self.b * y.b, self.n)
        else :
            return congruentRelation(self.a * y, self.b * y, self.n)

    def Proposition134(self) :
        """ 1.3.4. Proposition. Let 'a' and n > 1 be integers.
        There exists an integer 'b' such that ab  ≡  1 (mod n) if and only if (a,n) = 1.
        """
        # (a,n) = gcd (a,n) = 1
        v = lC([self.a, self.n])
        if v.gcd() == 1 :
            return v.egcd()
        else :
            return [None, None]

#1.3.5. Theorem. The congruence ax  ≡   b (mod n) has a solution if and only if b is divisible by d, where d=(a,n).
#If d | b, then there are d distinct solutions modulo n, and these solutions are congruent modulo n / d.

#1.3.6. Theorem. [Chinese Remainder Theorem] Let n and m be positive integers, with (n,m)=1.
#Then the system of congruences x  ≡   a (mod n)       x  ≡   b (mod m) has a solution.
#Moreover, any two solutions are congruent modulo mn.

#1.4.1. Definition. Let a and n>0 be integers.
#The set of all integers which have the same remainder as a when divided by n is called the congruence class of a modulo n, and is denoted by [a]n, where [a]n = { x ∈ Z | x  ≡  a (mod n) }.
#The collection of all congruence classes modulo n is called the set of integers modulo n, denoted by Zn.

#1.4.2 Proposition. Let n be a positive integer, and let a,b be any integers.
#Then the addition and multiplication of congruence classes given below are well-defined:
#        [a]n + [b]n = [a+b]n ,       [a]n[b]n = [ab]n.

#1.4.3. Definition. If [a]n belongs to Zn, and [a]n[b]n = [0]n for some nonzero congruence class [b]n, then [a]n is called a divisor of zero, modulo n.

#1.4.4. Definition. If [a]n belongs to Zn, and [a]n[b]n = [1]n, for some congruence class [b]n, then [b]n is called a multiplicative inverse of [a]n and is denoted by [a]n-1.
#In this case, we say that [a]n and [b]n are invertible elements of Zn, or units of Zn.

#1.4.5. Proposition. Let n be a positive integer.
#(a) The congruence class [a]n has a multiplicative inverse in Zn if and only if (a,n)=1.
#(b) A nonzero element of Zn either has a multiplicative inverse or is a divisor of zero.

#1.4.6. Corollary. The following conditions on the modulus n > 0 are equivalent:
#(1) The number n is prime.
#(2) Zn has no divisors of zero, except [0]n.
#(3) Every nonzero element of Zn has a multiplicative inverse.

#1.4.7. Definition. Let n be a positive integer.
#The number of positive integers less than or equal to n which are relatively prime to n will be denoted by φ (n).
#This function is called Euler's phi-function, or the totient function.

#1.4.8. Proposition. If the prime factorization of n is n = p1m1 p2m2 · · · pnmn , then
#             φ (n) = n(1-1/p1)(1-1/p2) · · · (1-1/pk).

#1.4.9. Definition. The set of units of Zn, the congruence classes [a]n, such that (a,n)=1, will be denoted by Zn×.

#The following theorem shows that raising any congruence class in Zn× to the power  φ (n) yields the congruence class of 1.
#It is possible to give a purely number theoretic proof at this point, but in Example 3.2.12 there is a more elegant proof using elementary group theory.

#1.4.11. Theorem. [Euler] If (a,n)=1, then a  φ  (n)  ≡  1 (mod n).

#1.4.12 Corollary. [Fermat] If p is prime, then ap  ≡   a (mod p), for any integer a.
